package com.michael.tree.rb;

public class PrintTree {
    private static int length = 3;
    public static void print(RBNode root, int height) {
        int count = (2 << height - 1) - 1;//最多节点数量
        int lines = height * 4 - 5;
        char[][] content = new char[lines][count * (length + 1)];
        for (int i = 0; i < lines; i++) {
            for (int j = 0; j < count * (length + 1); j++) {
                content[i][j] = ' ';
            }
        }
        //计算根节点的位置
        int index = count / 2;
        char[] chars = resolve(root);
        PrintNode printNode = new PrintNode(index * (length + 1), (index + 1) * (length + 1) -1, 1, root);
        System.arraycopy(chars, 0, content[0], index * (length + 1), chars.length);
        printNode(printNode, height, content);
        print(content);
    }
    private static char[] resolve(RBNode src){
        String tmp = "";
        if(src.color){
            tmp = src.key + "B";
        }else{
            tmp  = src.key + "R";
        }
        char[] srcChar = tmp.toCharArray();
        int offset = (length - srcChar.length)/2;
        char [] dst = new char[length];
        for (int i = 0; i < length; i++) {
            dst[i] = ' ';
        }
        System.arraycopy(srcChar,0,dst,offset,srcChar.length);

        return dst;
    }
    private static void print(char[][] lines){
        for (int i = 0; i < lines.length; i++) {
            System.out.println(lines[i]);
        }
    }
    private static void printNode(PrintNode node, int height, char[][] lines) {
        if (node.hasSun()) {
            int count = ((2 << (height - node.height) - 1) - 1) / 2;
            int amount = count * (length + 1);
            int startPos = node.startPos;
            int endPos = node.endPos;
            if (node.node.left != null) {
                lines[4 * (node.height - 1) + 1][startPos - 1] = '/';
                if (height - node.height > 1) {
                    for (int i = 0; i < amount - 1; i++) {
                        lines[4 * (node.height - 1) + 2][startPos -1 - (amount - 1) + i] = '-';
                    }
                    lines[4 * (node.height - 1) + 3][startPos - amount - 1] = '/';
                    //子节点
                    char[] chars = resolve(node.node.left);
                    System.arraycopy(chars, 0, lines[4 * (node.height - 1) + 4], startPos - amount-length-1 , chars.length);
                    PrintNode printNode = new PrintNode(startPos - amount- length-1, startPos - amount , node.height + 1, node.node.left);
                    printNode(printNode, height, lines);
                } else {
                    //子节点
                    String key = node.node.left.key + "";
                    char[] chars = resolve(node.node.left);
                    System.arraycopy(chars, 0, lines[4 * (node.height - 1) + 2], startPos - length - 1 , chars.length);
                }
            }
            if (node.node.right != null) {
                lines[4 * (node.height - 1) + 1][ endPos] = '\\';
                if (height - node.height > 1) {
                    for (int i = 0; i < amount - 1; i++) {
                        lines[4 * (node.height - 1) + 2][endPos + 1 + i] = '-';
                    }
                    lines[4 * (node.height - 1) + 3][endPos + amount ] = '\\';
                    //子节点
                    String key = node.node.right.key + "";
                    char[] chars = resolve(node.node.right);
                    System.arraycopy(chars, 0, lines[4 * (node.height - 1) + 4], endPos + amount+1, chars.length);
                    PrintNode printNode = new PrintNode(endPos + amount+1, endPos + amount+1 + length, node.height + 1, node.node.right);
                    printNode(printNode, height, lines);
                } else {
                    //子节点
                    String key = node.node.right.key + "";
                    char[] chars = resolve(node.node.right);
                    System.arraycopy(chars, 0, lines[4 * (node.height - 1) + 2], endPos + amount+1+1, chars.length);
                }
            }
        }
    }

    static class PrintNode {
        int startPos;
        int endPos;
        int height;
        RBNode node;

        public PrintNode(int startPos, int endPos, int height, RBNode node) {
            this.startPos = startPos;
            this.endPos = endPos;
            this.height = height;
            this.node = node;
        }

        public boolean hasSun() {
            return node.left != null || node.right != null;
        }
    }
}
